题解 P4008 【[NOI2003]文本编辑器】

发表于 | 更新于

链接

块状链表模板题，但出奇的恶心

由于一些操作会产生或删去一些块，所以对于块的产生与删去，块的编号用内存池分配

先给出几个操作，添加块($add$),查询属于哪个块($belong$),分裂($split$),合并($merge$)，具体细节看代码分析.

下面对题目给的操作进行分析

$1.Move~k$ 将光标移动到第 $k$个字符之后

直接移动即可

1
pos=read();

$2.Insert~n~s$ 在光标处插入长度为$n$的字符串$s$，光标位置不变

将插入串分块，最后一块(即剩余块,唯一的一块长度不一定是$size$的块)与它后面那一块判断一下，如果长度相加后$<size$,那么就合并.

并且我们很可能在块内插入，那我们就要将这个块从插入位置$split$,然后进行插入。

$3.Delete~n$ 删除光标后的n个字符，光标位置不变

先将两端所在的块分裂，然后直接删除，并且对两端分类出的块长度和进行判断，如果$<size$，就进行$merge$操作。

$4.Get~n$ 输出光标后的$n$个字符，光标位置不变

只需把左边块和右边块的需要部分给截出来，与中间完整的块拼在一起输出即可

$5.Prev$ 光标前移一个字符

直接移动即可

1
--pos;

$6.Next$ 光标后移一个字符

直接移动即可

1
++pos;

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define int long long
#define re register
#define inf 0x3f3f3f3f
#define N 100007
using namespace std;
struct node{
    int nx,size;
    char s[4500];
}t[9000];
char ans[8000000];
int cnt=1,tot,pos,pool[800000];
const int size=2007;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
inline int mod(){return pool[++cnt];}
inline void del(int x){pool[cnt--]=x;}//动态分配和回收内存池
void add(int x,int y,int len,char *s){//在编号为x的块后面加一个编号为y的块
    t[y].nx=t[x].nx;t[y].size=len;
    memcpy(t[y].s,s,sizeof(t[y].s));
    t[x].nx=y;
}
inline int belong(int &k){//查询属于哪个块
    int p=1;
    while (p&&k>t[p].size)k-=t[p].size,p=t[p].nx;
    return p;
}
void split(int x,int y){//将第x个块从y处分裂
    if (!x||y==t[x].size)return;//如果当前块不存在或从块中最后一个开始分割是没有意义的
    add(x,mod(),t[x].size-y,t[x].s+y);//t[x].s+y就相当于截去了t[x].s[1~(y-1)]
    t[x].size=y;
}
void merge(int x,int y){//合并x和y，把y接在x的后面,然后把y删除
    memcpy(t[x].s+t[x].size,t[y].s,t[y].size);
    t[x].size+=t[y].size;t[x].nx=t[y].nx;del(y);
}
void ins(int len,char *s){
    int k=pos,now=belong(k),w=now;
    split(now,k);int sum,nx;
    for (sum=0;sum+size<=len;sum+=size){
        add(now,nx=mod(),size,s+sum);
        now=nx;
    }
    if (len-sum>0){//如果剩余块的大小大于0 
        add(now,nx=mod(),len-sum,s+sum);
        if (t[now].size+t[nx].size<size&&nx)
            merge(now,nx);
    } 
    if (t[w].size+t[t[w].nx].size<size&&t[w].nx)
        merge(w,t[w].nx);
}
void dele(int len){
    int k=pos,now=belong(k);
    split(now,k);
    int i;
    for (i=t[now].nx;t[i].size<len&&i;i=t[i].nx)
        len-=t[i].size;
    split(i,len);
    for (int j=t[now].nx;j!=t[i].nx;j=t[now].nx)
        t[now].nx=t[j].nx,del(j);
    int q=t[i].nx;
    while (t[now].size+t[q].size<size&&q)merge(now,q),q=t[q].nx;
}
void print(int len){
    int k=pos;
    int now=belong(k);
    int nx=t[now].nx;
    int l=min(len,t[now].size-k);
    memcpy(ans,t[now].s+k,l);
    while (l+t[nx].size<=len&&nx){
        memcpy(ans+l,t[nx].s,t[nx].size);
        l+=t[nx].size;nx=t[nx].nx;
    }
    if (len-l>0&&nx)
        memcpy(ans+l,t[nx].s,len-l);
    ans[len]='\0';
    printf("%s\n",ans);
}
char s[8000000];
inline char gc(){
    char ch=getchar();
    while (ch!='M'&&ch!='I'&&ch!='D'&&ch!='G'&&ch!='P'&&ch!='N')ch=getchar();
    return ch;
}
signed main(){
    int T=read();
    for (int i=1;i<=2e5+7;++i)pool[i]=i;
    while (T--){
        char ch=gc();
        if (ch=='M'){//将光标移动到第 k个字符之后
            pos=read();
        }else if (ch=='I'){//在光标处插入长度为n的字符串s，光标位置不变
            int n=read();
            for (int i=0;i<n;++i){
                s[i]=getchar();
                if (s[i]<32||s[i]>126)--i;
            }
            ins(n,s);
        }else if (ch=='D'){//删除光标后的n个字符
            dele(read());
        }else if (ch=='G'){//输出光标后的n个字符
            print(read());
        }else if (ch=='P'){
            --pos;
        }else{
            ++pos;
        }
    }
    return 0;
}